
/**
 * 
 * 【分糖果】最少分至一颗糖果的次数
 * 
 * 题目描述

小明从糖果盒中随意抓一把糖果，每次小明会取出一半的糖果分给同学们。

当糖果不能平均分配时，小明可以选择从糖果盒中（假设盒中糖果足够）取出一个糖果或放回一个糖果。

小明最少需要多少次（取出、放回和平均分配均记一次），能将手中糖果分至只剩一颗。

输入描述
抓取的糖果数（<10000000000）：15

输出描述
最少分至一颗糖果的次数：5

用例
输入	15
输出	5
说明	
15+1=16;
16/2=8;
8/2=4;
4/2=2;
2/2=1;
 */

import java.util.Scanner;

/**
  * 
  题目分析
本题由于是每次折半，因此本题数量级即便很大，也不怕超时。

没有了超时的后顾之忧，本题，直接可以暴力逻辑求解，假设输入的是num，分配次数count初始为0，那么：

如果num % 2 == 0，则可以直接折半，此时分配次数count++， num /= 2
如果num % 2 !=0，则不可以直接折半，此时需要开两个分支：
取出一个糖，即num += 1，然后分配次数count++，之后继续前面折半逻辑
放回一个糖，即num -= 1，然后分配次数count++，之后继续前面折半逻辑
最终我们只需要在众多分支中，取最少的count即可。
  */

public class 分糖果 {
    
    public static void main(String[] args) {
        
        try{


            Scanner scanner = new Scanner(System.in);

            int count = scanner.nextInt(); //糖果数量
            int divideCount = 0;

            int[] tempCount = {Integer.MAX_VALUE};

            doDivide(count, divideCount, tempCount);

            System.out.println(tempCount[0]);

        }catch(Exception e){

            e.printStackTrace();
        }
    }

    private static void doDivide(int count, int divideCount, int[] tempCount){

        System.out.println("count="+count);
        if(1 == count){

            tempCount[0] = Math.min(divideCount, tempCount[0]);

            return;
        }

        if(count % 2 == 0){

            doDivide(count / 2, divideCount + 1, tempCount);

        } else{

            //加 1 和 减 1 的情况同时进行，上面谁先执行到 count ==1 都回停止
            doDivide(count + 1, divideCount + 1, tempCount);
            doDivide(count - 1, divideCount + 1, tempCount);

        }

    }
}
